package LeetCode_SingleLinkedlist;

/**
 * Created with IntelliJ IDEA.
 * Description: 链表的回文结构
 * User: 阿宾
 * Date: 2024-11-06
 * Time: 21:19
 */
public class Demo6 {
    public static class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public static boolean chkPalindrome(ListNode A) {
        //空链表或只有一个元素的链表始终都是回文结构
        if (A == null || A.next == null) {
            return true;
        }
        //1.找到链表中间节点
        ListNode fast = A;
        ListNode slow = A;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //此时slow所指向的就是链表中点
        //2.反转后半段链表，即原地逆置
        ListNode cur = slow.next;//用来遍历链表
        ListNode pre = slow.next;
        slow.next = null;
        while(cur != null){
            pre = cur.next;
            cur.next = slow;
            slow = cur;
            cur = pre;
        }
        //此时slow是已经反转好的后半段链表
        //3.对前后两段进行比较
        while (A != null && slow != null) {
            if(A.val != slow.val){
                return false;
            }
            A = A.next;
            slow = slow.next;
        }
        return true;
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(12, new ListNode(23,new ListNode(56,new ListNode(23,new ListNode(12)))));
        Boolean result = chkPalindrome(l1);
        System.out.println(result);
    }
}
